package com.mzy.linear_struct.subject;

import java.util.Arrays;

/**
 * @Author: codermzy
 * @Date: 2024/04/22/下午2:39
 * @Description:
 */
public class 排序数组912 {


    static class Solution {
        public int[] sortArray(int[] nums) {
            partition(nums, 0, nums.length - 1);
            return nums;
        }

        private void partition(int[] nums, int left, int right) {
            if (left >= right) return;
            int pivot = nums[right];

            int i = left, j = right - 1;

            while (i <= j) {

                while (nums[i] < pivot) {
                    i++;
                }

                while (j >= 0 && nums[j] > pivot) {
                    j--;
                }

                if (i <= j) {
                    swap(nums, i, j);
                    i++;
                    j--;
                }
            }

            swap(nums, i, right);

            partition(nums, left, j);
            partition(nums, i + 1, right);
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] nums = {5, 1, 1, 2, 0, 0};
        new Solution().sortArray(nums);
        System.out.println(Arrays.toString(nums));
    }
}
